package main

import (
	"godemo/utils"
)

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

//
func preOrder(tree *Node) {
	if tree != nil {
		println(tree.Val)
		preOrder(tree.Left)
		preOrder(tree.Right)
	}
}

//
func inOrder(tree *Node) {
	if tree != nil {
		inOrder(tree.Left)
		println(tree.Val)
		inOrder(tree.Right)
	}
}

//
func postOrder(tree *Node) {
	if tree != nil {
		postOrder(tree.Left)
		postOrder(tree.Right)
		println(tree.Val)
	}
}

func main() {
	n1 := Node{Val: 5}
	n2 := Node{Val: 6}
	n3 := Node{Val: 7}
	n4 := Node{Val: 8}
	n1.Left = &n2
	n1.Right = &n3
	n2.Left = &n4
	println("preOrder")
	preOrder(&n1)
	println("inOrder")
	inOrder(&n1)
	println("postOrder")
	postOrder(&n1)

	nums := []int{6, 3, 8, 2, 5, 1, 7, 9, 4, 0}
	tree := genBST(nums)
	println("preOrder")
	preOrder(tree.Root)

	println("inOrder")
	inOrder(tree.Root)

	println("MirrorATree")
	MirrorATree(tree.Root)

	println("preOrder")
	preOrder(tree.Root)

	println("inOrder")
	inOrder(tree.Root)

	h := RecHight(tree.Root)
	println("RecHight", h)

}

// Tree Tree
type Tree struct {
	Root *Node
}

// MirrorATree 翻转二叉树
func MirrorATree(node *Node) *Node {
	if node == nil {
		return node
	}

	tmp := MirrorATree(node.Left) // 注意指针操作
	node.Left = MirrorATree(node.Right)
	node.Right = tmp
	return node
}

// RecHight 二叉树高度 递归
func RecHight(node *Node) int {
	if node == nil {
		return 0
	}

	left := RecHight(node.Left) // 注意指针操作
	right := RecHight(node.Right)
	return utils.Max(left, right) + 1
}

// Insert BST 二叉搜索树的插入
func (t *Tree) Insert(val int) {
	node := &Node{Val: val}
	if t.Root == nil {
		t.Root = node
	} else {
		tmp := t.Root
		for {
			if val < tmp.Val {
				if tmp.Left == nil {
					tmp.Left = node
					return
				}
				tmp = tmp.Left
			} else if val > tmp.Val {
				if tmp.Right == nil {
					tmp.Right = node
					return
				}
				tmp = tmp.Right
			}
		}

	}
}

// 根据数组生成二叉搜索树
func genBST(nums []int) (tree *Tree) {
	tree = &Tree{}
	for _, item := range nums {
		tree.Insert(item)
	}
	return tree
}
